The present invention relates to data compression apparatus and methods in general, and in particular to a novel data compression apparatus and method for reducing the number of bits of data transmitted between a data source and a data utilization device.
The term data compression is commonly applied to a number of basically different types of apparatus and processes for performing data reduction. A first major classification of these processes is between irreversible and reversible processes. An irreversible process is one in which a certain portion of input information is irreversibly lost during data compression. Such processes include filtering, limiting, statistical moment estimation, etc. The class of reversible processes can be described as information-preserving. An information-preserving data compression process is one that, when applied to input data, reduces the amount of energy required to transmit characteristics of the data without reducing the information content of the data.
Another major distinction may be made between types of data -- e.g., that for which statistical distribution information is known in advance, and that for which this information is not known. Examples of the first type are: 1) data obtained from video data encoding, possibly performed by one or two-dimensional run length processes, 2) message alphabets with known probability distributions, possibly obtained by Shannon-Fano-Huffman redundancy reduction processes, and 3) time-sampled instrumentation data, possibly performed by polynomial approximation or statistical prediction processes. A major example of input data about which no information is available is transmitted or stored computer data. Blocks of such data typically comprise a binary code of fixed length having m bits with the probability of occurrence of 2.sup.m binary patterns equal to one. Such a data block is typically composed of some fixed number of bits of useful data n, and another fixed number p of one of several well-known Forward Error Correcting codes with n + p = m. Presently, however, the amount of data compression that can be achieved with processes in which no information is available in advance about the original data is limited.